/*
 * @lc app=leetcode.cn id=32 lang=cpp
 *
 * [32] 最长有效括号
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>

using namespace std;
// @lc code=start 
// dp[i] = i - dp[i-1] -1
class Solution {
public:
    int longestValidParentheses(string s) {
        int ret = 0;
        int n = s.length();
        if(n < 2) {
            return 0;
        }
        vector<int> dp(n,0);
        for(int i = 1;i < n;i++) {
            //  if(s[i] == ')') {
            //      if (s[i - 1] == '(') {
            //         dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
            //     } else if (i - dp[i - 1] > 0 && s[i - dp[i - 1] - 1] == '(') {
            //         dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
            //     }
            //  }
            if (s[i]==')' && i-dp[i-1]-1>=0 && s[i-dp[i-1]-1]=='(') {
                dp[i]=dp[i-1]+(i-dp[i-1]-2>=0?dp[i-dp[i-1]-2]:0)+2;
            }
               
             ret = max(ret,dp[i]);
        }
        return ret;
    }
};
// @lc code=end

